#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root)
    {
        vector<vector<int>> res;
        vector<int> tmp;
        queue<TreeNode* > qe;

        if (root == nullptr)
            return res;

        int count = 1;
        qe.push(root);
        tmp.push_back(root->val);
        res.push_back(tmp);
        tmp.clear();


        int flag = 0;
        int num = count;
        count = 0;
        while (!qe.empty())
        {
            while (num--)
            {
                if (qe.front()->left != nullptr)
                {
                    count++;
                    qe.push(qe.front()->left);
                }

                if (qe.front()->right != nullptr)
                {
                    count++;
                    qe.push(qe.front()->right);
                }

                if (qe.front() == root)
                {
                    flag = 1;
                    qe.pop();
                }
                else
                {
                    flag = 0;
                    tmp.push_back(qe.front()->val);
                    qe.pop();
                }
            }
            if (flag != 1)
            {
                res.push_back(tmp);
                tmp.clear();
            }
            num = count;
            count = 0;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

int main()
{
	TreeNode* root = new TreeNode(3, nullptr, nullptr);
	root->left = new TreeNode(9, nullptr, nullptr);
	root->right = new TreeNode(20, nullptr, nullptr);
	root->right->left = new TreeNode(15, nullptr, nullptr);
	root->right->right = new TreeNode(7, nullptr, nullptr);

	Solution s1;
    s1.levelOrderBottom(root);
	return 0;
}